\section{Implementaci\'on}

\subsection{Estructura del c\'odigo}
La organizaci\'on del c\'odigo fuente utilizado para este trabajo se basa en Maven. El
c\'odigo fuente entregado por la c\'atedra ya estaba empaquetado para Maven y ven\'ia
provisto de su \textit{pom.xml} con su correspondiente nombre de artefacto y versionado.
Lo desarrollado por el grupo tiene como dependencia de Maven a este proyecto, entonces 
para poder compilar el c\'odigo fuente se necesita tener esta librer\'ia instalada.\\

El c\'odigo fuente desarrollado por el grupo se divide en dos proyectos de Maven.
\begin{itemize}
\item \textbf{ubadb-grupo6-strategies}: en este proyecto se implementaron las estrategias MRU y LRU 
que fueron solicitadas por la c\'atedra. Tambi\'en se implementaron otras estrategias 
propuestas por el grupo. Se hizo enf\'asis en la documentaci\'on de este proyecto ya
que contiene estrategias que pueden ser re-utlizables en el futuro.
\item \textbf{ubadb-grupo6-benchmark}: en este proyecto se implementaron los procesos para
medir la eficiencia de las estrategias mencionadas. Este proyecto tiene como dependencia el anterior.
\end{itemize}
  
   
\subsection{Estrategias nuevas}
La \'unica estrategia existente en el c\'odigo provisto por la c\'atedra correpond\'ia a la estrategia FIFO 
(el primero en entrar es el primero en salir). Las estrategias implementadas por el grupo tomaron como base esta
implementaci\'on de dos clases: una para la estrategia y otra para agregarle informaci\'on al \textit{BufferFrame}.
\begin{itemize}
\item \textbf{MRU}: esta estrategia registra para cada frame en memoria la fecha en la que fue referenciado por \'ultima vez. Para seleccionar la v\'ictima itera a trav\'es de todas las p\'aginas en memoria y selecciona la que fue referenciada m\'as recientemente.
\item \textbf{LRU}: al igual que MRU, lleva un registro de la \'ultima vez que fue accedida cada p\'agina y escoge como v\'ictima a la que fue referenciada menos recientemente.
\item \textbf{Best}: esta estrategia implementa el algoritmo de reemplazo de p\'agina \'optimo de Belady \cite{bel66}. Utiliza el conocimiento de la secuencia completa de pedidos antes de ser ejecutada, por lo tanto no es \'util desde el punto de vista pr\'actico
pero s\'i para comparar con el resto de las estrategias. Selecciona como v\'ictima la p\'agina con que tiene el tiempo hasta a su pr\'oxima referencia mas grande, o bien a un p\'agina que no va a volver a ser referenciada.
\item \textbf{Random}: esta estrategia devuelve como v\'ictima un frame al azar. Ser\'a usada para 
comparar eficiencia con otras estrategias, dada la falta de l\'ogica en esta estrategia ser\'a considerada como un ``piso'' de la eficiencia. 
\end{itemize}
Para seguir manteniendo el orden de c\'odigo estas estrategias se implementaron cada un en un sub-paquete de java propio 
bajo \textit{ubadb.components.bufferManager.bufferPool.replacementStrategies}.

\subsection{Tests de unidad}

Para probar la correctitud de cada una de las estrategias utilizadas, se realizaron una serie de tests de unidad. Estas pruebas se encuentran en los paquetes

\textit{ubadb.core.components.bufferManager.bufferPool.replacementStrategies.$<$estrategia$>$}

de acuerdo al formato dado por la c\'atedra para el ejemplo de FIFO.

\subsection{Buffers por tabla}
El \textit{BufferPool} que soporta distintas estrategias por tabla se encuentra implementado
en la clase \textit{ubadb.core.components.bufferManager.bufferPool.PerTableBufferPool}. 
El comportamiento desado se logra relacionando mediante una tabla de hash una tabla a 
un \textit{BufferPool} 

\subsection{Mediciones}
Para comparar las distintas estrategias para el \textit{MemoryBuffer} se consider\'o medir
la tasa de aciertos (\textit{hit rate}) de cada una de ellas ante las mismas secuencias 
de pedidos y liberaciones de p\'aginas (trazas). De cada \textit{traza} se entiende la tasa
de aciertos como el porcentaje de \'paginas pedidas donde no se tuvo que acceder a disco
porque ya estaba cargada en el \textit{MemoryBuffer}. Para poder calcular este resultado
se midieron la cantidad de pedidos de paginas (\textit{requests}) y la cantidad de veces
que se tuvo que leer una p\'agina en el disco (\textit{fails}). Con estas dos magintudes
se define la \textit{hit rate} como: \\
\begin{center}
$hit rate = \frac{requests-fails}{requests}$  
\end{center}
La \textit{hit rate} se puede considerar como un porcentaje multiplic\'andolo por $100$.

\subsubsection{Buffer compartido - Escenarios 1 y 2}
En las trazas de los escenarios 1 y 2 hay muy pocas repeticiones de un mismo request a una page,
entonces si se prueba cada traza individualmente la cantidad de aciertos va ser muy baja 
ya que la mayor'ia de las p'aginas se piden una sola vez y luego no se vuelven a pedir. \\
Para poder probar las distintas estrategias en un modo \textit{SingleBuffer} 
con casos mas diversos y que generen un resultado interesante se utilizaron combinaciones de las
trazas de los escenarios 1 y 2. 

Utilizando el modelo de los archivos provistos se implementaron funciones que generan las distintas trazas: 
\begin{itemize}
\item \textit{File Scan}: traza que simula la lectura secuencial de p\'aginas contiguas. Utiliza el m\'etodo \textit{createTracesFileScan} de la clase TraceUtil.
\item \textit{Index Scan Clustered}: traza que simula la lectura de la estructura que funciona como \'indice y luego de la secuencia de p\'aginas ordenadas. Utiliza el m\'etodo \textit{createTraceScanClustered} de la clase TraceUtil.
\item \textit{Index Scan Unclustered}: traza que simula la lectura de la estructura que funciona como \'indice y luego de la secuencia de p\'aginas desordenadas en el archivo. Utiliza el m\'etodo \textit{createTraceScanUnclustered} de la clase TraceUtil.
\item \textit{BNLJ}: traza que simula un BNLJ. Utiliza el m\'etodo \textit{createTracesBNLJ} de la clase TraceUtil.
\end{itemize}
A partir de estas trazas ``puras'' se generaron tambi\'en trazas compuestas por una secuencia aleatoria de una cierta cantidad de ellos. Esta estrategia de generaci\'on se encuentra implementada en el m\'etodo \textit{generateRandomTrace} de TraceUtil.

\subsubsection{Buffers por tabla - Escenario 3}
El parser de los archivos de trazas se implement'o en el m'etodo \textit{readTrace} de la clase \textit{TraceUtil}.
Los archivos de trazas se incluyen en el directorio \textit{src/main/resources} del proyecto
de \textit{benchmark}. 

